package leetcode.weekly.week344;

import java.util.LinkedList;
import java.util.Queue;

//Solution4Test
public class Solution4 {
	public int minIncrements(int n, int[] cost) {
		Queue<Integer> queue = new LinkedList<>();
		queue.add(1);
		int ans = 0;
		while (!queue.isEmpty()) {
			int size = queue.size();
			Queue<Integer> next = new LinkedList<>();
			int max = Integer.MIN_VALUE;
			while (size > 0) {
				int cur = queue.poll();
				int costs = cost[cur - 1];
				max = Math.max(max, costs);
				if (cur * 2 < n) {
					next.add(cur * 2);
				}
				if ((cur * 2 + 1) <= n) {
					next.add(cur * 2 + 1);
				}
				queue.add(cur);
				size--;
			}
			size = queue.size();
			while (size > 0) {
				int cur = queue.poll();
				int costs = cost[cur - 1];
				ans += max - costs;
				size--;
			}
			queue = next;
		}
		return ans;

	}

}
